#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int main()
{
	int n;
	scanf("%d", &n);

	int a = 0, b = 0, mut = 1;
	int i;
	for (i = 1; i <= n; i++)
	{
		scanf("%d %d", &a, &b);
		for (int j = 1; j <= b; j++)
		{
			mut = mut * a;
			if (mut > 1000)
				mut = mut % 1000;
		}
		printf("%d\n", mut);
		mut = 1;
	}
	return 0;
}